package algorithm.sort.insert;

public class BinaryInsertSort {
    public static void sort(int[] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = i; j > 0; j--) {
                int toInsertData = data[j];
                int toInsertIndex = searchIndex(data, toInsertData, 0, j - 1);
                for (int k = j; k > toInsertIndex; k--) {
                    data[k] = data[k - 1];
                }
                data[toInsertIndex] = toInsertData;
            }
        }
    }

    private static int searchIndex(int[] data, int toInsertData, int start, int end) {
        while (start <= end) {
            int mid = (end + start) / 2;
            if (toInsertData < data[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

}
